﻿#pragma once
#include<iostream>
using namespace std;

enum Colour
{
	RED,
	BLACK
};

//template<class K,class V>
//struct rbTreeNode
//{
//	pair<K, V> _kv;
//	rbTreeNode<K, V>* _left;
//	rbTreeNode<K, V>* _right;
//	rbTreeNode<K, V>* _parent;
//	Colour _col;
//
//	rbTreeNode(const pair<K,V>& kv)
//		: _kv(kv)
//		, _left(nullptr)
//		, _right(nullptr)
//		, _parent(nullptr)
//	{}
//};

template<class T>
struct rbTreeNode
{
	T _data;
	rbTreeNode<K, V>* _left;
	rbTreeNode<K, V>* _right;
	rbTreeNode<K, V>* _parent;
	Colour _col;

	rbTreeNode(const T& data)
		: _data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

template<class T,class Ref,class Ptr>
struct rbTreeIterator
{
	typedef rbTreeNode<T> Node;
	typedef rbTreeInterator<T, Ref, Ptr> Self;

	Node* _node;

	rbTreeIterator(Node* node,Node* root)
		:_node(node)
		,_root(root)
	{}

	Self operator++()
	{
		if (_node->_right)
		{
			Node* min = _node->_right;
			while (min->_left)
			{
				min = min->_left;
			}

			_node = min;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	Self operator--()
	{
		if (_node == nullptr)
		{
			Node* rightMost = _root;
			while (rightMost && rightMost->_right)
			{
				rightMost = rightMost->_right;
			}

			_node = rightMost;
		}
		else if (_node->_left)
		{
			Node* rightMost = _node->_left;
			while (rightMost->_right)
			{
				rightMost = rightMost->_right;
			}

			_node = rightMost->_right;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;

			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
};

template<class K,class T,class KeyOfT>
class rbTree
{
	typedef rbTreeNode<T> Node;
public:
	typedef rbTreeInterator<T, &T, T*> Iterator;
	typedef rbTreeInterator<T, const& T, const T*> ConstIterator;

	Iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return Iterator(cur);
	}

	Iterator end()
	{
		return Iterator(nullptr);
	}

	pair<Iterator,bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			//return pair<Interator,bool>(Interator(_root,_root),true);
			return { Interator(_root,_root),true };//隐式类型转换
		}

		KeyOfT kot;
		Node* cur = _root;
		Node* parent = nullptr;

		while (cur)
		{
			if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return { Iterator(cur,_root),false };
			}
		}
		//cur走到插入位置
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED;

		if (kot(parent->_data) > kot(data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;

			if (parent = grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
						 //  g
						//p     u  存在必为从下变换上来
					  //c
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
							//   g
							//p     u  存在必为从下变换上来
							//  c
						RotateL(parent);
						RotateR(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}

			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (parent->_right == cur)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
					//  g
					//u   p
					//  c   c
			}

		}
		_root->_col = BLACK;

		return { iterator(newnode,_root),true };
	}

	
	//bool Insert(const pair<K, V>& kv)
	//{
	//	if (_root == nullptr)
	//	{
	//		_root = new Node(kv);
	//		_root->_col = BLACK;
	//		return true;
	//	}
	//	Node* parent = nullptr;
	//	Node* cur = _root;
	//	while (cur)
	//	{
	//		if (cur->_kv.first < kv.first)
	//		{
	//			parent = cur;
	//			cur = cur->_right;
	//		}
	//		else if (cur->_kv.first > kv.first)
	//		{
	//			parent = cur;
	//			cur = cur->_left;
	//		}
	//		else
	//		{
	//			return false;
	//		}
	//	}
	//	cur = new Node(kv);
	//	// 新增结点。颜⾊红⾊给红⾊
	//	cur->_col = RED;
	//	if (parent->_kv.first < kv.first)
	//	{
	//		parent->_right = cur;
	//	}
	//	else
	//	{
	//		parent->_left = cur;
	//	}
	//	cur->_parent = parent;
	//	while (parent && parent->_col == RED)
	//	{
	//		Node* grandfather = parent->_parent;
	//		// g
	//		// p u
	//		if (parent == grandfather->_left)
	//		{
	//			Node* uncle = grandfather->_right;
	//			if (uncle && uncle->_col == RED)
	//			{
	//				// u存在且为红 -》变⾊再继续往上处理
	//				parent->_col = uncle->_col = BLACK;
	//				grandfather->_col = RED;
	//				cur = grandfather;
	//				parent = cur->_parent;
	//			}
	//			else
	//			{
	//				// u存在且为⿊或不存在 -》旋转+变⾊
	//				if (cur == parent->_left)
	//				{
	//					// g
	//					// p u
	//					//c
	//					//单旋
	//					RotateR(grandfather);
	//					parent->_col = BLACK;
	//					grandfather->_col = RED;
	//				}
	//				else
	//				{
	//					// g
	//					// p u
	//					// c
	//					//双旋
	//					RotateL(parent);
	//					RotateR(grandfather);
	//					cur->_col = BLACK;
	//					grandfather->_col = RED;
	//				}
	//				break;
	//			}

	//		}
	//		else
	//		{
	//			// g
	//			// u p
	//			Node* uncle = grandfather->_left;
	//			// 叔叔存在且为红，-》变⾊即可
	//			if (uncle && uncle->_col == RED)
	//			{
	//				parent->_col = uncle->_col = BLACK;
	//				grandfather->_col = RED;
	//				cur = grandfather;
	//				parent = cur->_parent;
	//			}
	//			else // 叔叔不存在，或者存在且为⿊
	//			{
	//				// 情况⼆：叔叔不存在或者存在且为⿊
	//				// 旋转+变⾊
	//				// g
	//				// u p
	//				// c
	//				if (cur == parent->_right)
	//				{
	//					RotateL(grandfather);
	//					parent->_col = BLACK;
	//					grandfather->_col = RED;
	//				}
	//				else
	//				{
	//					// g
	//					// u p
	//					// c
	//					RotateR(parent);
	//					RotateL(grandfather);
	//					cur->_col = BLACK;
	//					grandfather->_col = RED;
	//				}
	//				break;
	//			}
	//		}
	//	}

	//	_root->_col = BLACK;
	//	return true;
	//}


	/*bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		
		if (_root->_col == RED)
			return false;
		
		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				refNum++;
			}
			cur = cur->_left;
		}
		
		return check(_root, 0, refNum);
	}*/

	/*bool IsBalance()
	{
		if (_root == nullptr)
			return true;

		if (_root->_col == RED)
			return false;

		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				refNum++;
			}

			cur = cur->_left;
		}

		return check(_root, 0, refNum);
	}*/

	void RotateL(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* pParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			subL = _root;
			subL->_parent = nullptr;
		}
		else
		{
			if (pParent->_left == parent)
			{
				pParent->_left = subL;
			}
			else
			{
				pParent->_right = subL;
			}

			subL->_parent = pParent;
		}
	}

	void RotateR(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* pParent = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;
		if (parent == _root)
		{
			subR = _root;
			subR->_parent = nullptr;
		}
		else
		{
			if (pParent->_left == parent)
			{
				pParent->_left = subR;
			}
			else
			{
				pParent->_right = subR;
			}

			subR->_parent = pParent;
		}
	}

	/*void InOrder()
	{
		_InOrder(_root);
	}*/
private:
	Node* _root = nullptr;

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		//cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	/*bool check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			if (refNum != blackNum)
			{
				cout << "存在黑色节点不相等的路径" << endl;
				return false;
			}
			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在连续的红色节点" << endl;
			return false;
		}

		if (root->_col == BLACK)
		{
			blackNum++;
		}

		return check(root->_left, blackNum, refNum)
			&& check(root->_right, blackNum, refNum);
	}*/

	/*bool check(Node* root, int blackNum, int refNum)
	{
		if (root == nullptr)
		{
			if (refNum != blackNum)
			{
				cout << "黑色节点存在不相等路径" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在连续的红色结点" << endl;
			return false;
		}

		if (root->_col == BLACK)
		{
			blackNum++;
		}

		return check(root->_left, blackNum, refNum)
			&& check(root->_right, blackNum, refNum);
	}*/
};




















































































































